<?php
/**
 * @title 98. 验证二叉搜索树 - 递归
 * @author start2004
 */

// ini_set("memory_limit", "128M");

class Solution {

    /**
     * @param TreeNode $root
     * @return Boolean
     */
    function isValidBST($root) {
        /**
         * @return
         */
        return $this->find($root, null, null);
    }

    /**
     * @title 检查是否匹配
     * @author start2004
     * @since 2020-08-13 Created
     *
     * @param $root
     * @param int $max
     * @param int $min
     */
    public function find($root, $max=0, $min=0){
        /**
         * @since 2020-08-13 节点值
         */
        $val = $root->val;
        // echo "root->val={$val}, max={$max}, min={$min}", PHP_EOL;

        /**
         * @since 2020-08-13 左节点存在
         */
        $left = $root->left;
        if($left !== null){
            // echo "left=", $left->val, PHP_EOL;

            /**
             * @since 2020-08-13 节点的左子树只包含小于当前节点的数
             * @since 2020-08-13 有最小值, 2个数区间之间
             * @since 2020-08-13 无最小值, 小于root->val
             */
            if(($left->val < $val) AND (($min===null) OR (($min !==null AND $left->val > $min)))){
                /**
                 * @since 2020-08-13 检查左子树
                 */
                $result = self::find($left, $val, $min);
                if($result === false){
                    return false;
                } else {}
            } else {
                return false;
            }
        } else {}

        /**
         * @since 2020-08-13 右节点存在
         */
        $right = $root->right;
        if($right !== null){
            // echo "right=", $right->val, PHP_EOL;

            /**
             * @since 2020-08-13 节点的右子树只包含大于当前节点的数
             * @since 2020-08-13 有最小值, 2个数区间之间
             * @since 2020-08-13 无最小值, 小于root->val
             */
            if(($right->val > $val) AND (($max===null) OR (($max !==null AND $right->val < $max)))){
                /**
                 * @since 2020-08-13 检查右子树
                 */
                $result = self::find($right, $max, $val);
                if($result === false){
                    return false;
                } else {}
            } else {
                return false;
            }
        } else {}

        /**
         * @return
         */
        return true;
    }
}



/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.13.php
 */
$datas = [
    // [2,1,3],
    // [5,1,4,null,null,3,6],
    // [10,5,15,null,null,6,20],
    [3,1,5,0,2,4,6],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->isValidBST($xhprof->tree($data));
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
